package com.cyx;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

/**
 * @author 陈裕星
 * @version 1.0
 * 给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
 * candidates 中的每个数字在每个组合中只能使用 一次 。
 * 输入: candidates = [10,1,2,7,6,1,5], target = 8,
 * 输出:
 * [
 * [1,1,6],
 * [1,2,5],
 * [1,7],
 * [2,6]
 * ]
 */
public class 组合总和2 {
    static List<List<Integer>> res = new ArrayList<>();
    static List<Integer> tmp = new ArrayList<>();
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] candidates = new int[n];
        for (int i = 0; i < n; i++) {
            candidates[i] = sc.nextInt();
        }
        int target = sc.nextInt();

        //排序，方便操作
        Arrays.sort(candidates);

        backtrack(candidates,0,target);
        System.out.println(res.toString());
    }
    static void backtrack(int[] candidates,int start,int target){
        if(target == 0){
            res.add(new ArrayList<>(tmp));
            return;
        }

        for (int i = start; i < candidates.length; i++) {
            //剪枝
            if (candidates[i] > target ) break;
            if (i > start && candidates[i] == candidates[i-1]) continue;

            tmp.add(candidates[i]);
            backtrack(candidates,i + 1,target - candidates[i]);
            tmp.remove(tmp.size()-1);
        }
    }
}
